package com.kfm.am;

import java.util.Random;

// 设计一个类，这个类对外提供三个方法
// 计算给定n之内的所有素数和
// 将给定的数组进行插入排序
// 给定一个排好序的数组和一个数字，使用二分查找输入数字所在的下标，如果不存在返回-1
public class Utils {

    /**
     * 计算 1-n 的素数和
     *
     * @param n 要计算的范围
     * @return 该范围内的素数和
     */
    public static int sumOfPrime(int n) {
        int sum = 0;
        outer:
        for (int i = 1; i <= n; i++) {
            int count = 0;
            for (int j = 1; j < i; j++) {
                if (i % j == 0) {
                    count++;
                }
                if (count > 1) {
                    continue outer;
                }
            }
            if (count == 1) {
                sum += i;
            }
        }
        return sum;
    }

    /**
     * 将给定数组进行插入排序
     * @param arr 要排序的数组
     */
    public static void insertSort(int[] arr) {
        // 插入排序 从下标为1 开始 和前面的一一比较 如果比前面的小 前面的后移 最后把当前的值放到最后一个值的位置
        for (int i = 0; i < arr.length - 1; i++) {
            int temp = arr[i + 1];
            int index = i;
            while (index >= 0 && temp < arr[index]) {
                arr[index + 1] = arr[index];
                index --;
            }
            arr[index + 1] = temp;
        }
    }

    /**
     * 二分查找指定值在数组中的下标
     * @param arr 要查找的数组
     * @param key 要查询的数字
     * @return 该数字所在的下标，如果存在返回下标，不存在返回 -1
     */
    public static int binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }


    public static int rand() {
        return new Random().nextInt(39) + 1;
    }

}
